package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

var successor *ListNode

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == 1 {
		return reversePreN(head, right)
	}
	head.Next = reverseBetween(head.Next, left-1, right-1)
	return head
}

func reversePreN(head *ListNode, n int) *ListNode {
	if n == 1 {
		successor = head.Next
		return head
	}
	last := reversePreN(head.Next, n-1)
	head.Next.Next = head
	head.Next = successor
	return last
}

func main() {

	head := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}
	m := 2
	n := 4

	printListNode(reverseBetween(head, m, n))

}

func printListNode(tobePrint *ListNode) {
	for i := 1; ; {
		if tobePrint == nil {
			break
		}
		fmt.Printf("[%v] <%p> Val:%v -> <%p>\n", i, tobePrint, tobePrint.Val, tobePrint.Next)
		tobePrint = tobePrint.Next
		i++
	}
}
